﻿// 分析外星信号  ITES.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>

/*
https://algospot.com/judge/problem/read/ITES
数霸是参与跨世界大规模项目ITES@home的一部分，该项目旨在研究来自外星的射电信号。这些来自外星的信号经过预处理后，以自然数序列的形式给出，每个数字都在[1,10000]范围内。现在，数霸想要确定这些信号到底是简单的噪声还是具有有意义的模式。他注意到，在信号的子序列中，和为K的情况特别多。这里的子序列指的是连续的一段数字。例如，在序列{1,4,2,1,4,3,1,6}中，和为7的子序列共有5个：{1,4,2}、{4,2,1}、{2,1,4}、{4,3}和{1,6}。需要注意的是，这些子序列可以重叠。

K对外星人来说是否具有意义？为了验证数霸的假设，当给定长度为N的信号记录时，请编写一个程序来计算和为K的子序列的数量。

输入生成:
由于输入规模很大，因此在这个问题中，不会直接输入信号记录，而是通过以下方式在程序内生成：

A[0] = 1983
A[i] = (A[i-1] * 214013 + 2531011) % 232

其中，第i(1 <= i <= N)个输入信号为A[i-1] % 10000 + 1。问题的解决方式与生成输入的方式无关。根据这个规则，前5个信号分别是1984、8791、4770、7665和3188。

输入:
输入文件的第一行包含一个整数C (1 <= C <= 20)，表示测试用例的数量。接下来的C行，每行包含两个整数K(1 <= K <= 5,000,000)和N(1 <= N <= 50,000,000)，表示目标和和信号记录的长度。

输出:
对于每个测试用例，输出一行，表示前N个信号中和为K的子序列的数量。

示例输入:
3
8791 20
5265 5000
3578452 5000000

示例输出:
1
4
1049
*/
int main()
{
    std::cout << "Hello World!\n";
}

 